Computer vision

Q1 圖片水平翻轉 (Image Horizontal Flip)

出題機率：★★★★★ 原因： 這是影像處理最入門的題目，考驗你對二維陣列（2D Array）座標的理解，以及「交換數值 (Swap)」的基本邏輯。

情境： App 有一個「鏡像」功能，使用者點擊後，自拍照片要左右相反。

A1

code
FUNCTION FlipImageHorizontal(
    width: Integer,
    height: Integer,
    pixel: 2D Array
) -> OUTPUT: 2D Array

    FOR y FROM 0 TO height-1 DO
        FOR x FROM 0 TO (width/2) - 1 DO
            left_pixel = pixel[y][x]
            right_pixel = pixel[y][width - 1 - x]

            pixel[y][x] = right_pixel
            pixel[y][width - 1 - x] = left pixel
        END FOR
    END FOR

    RETURN pixel

END FUNCTION

Q2 Top-K 相似圖片搜尋 (Top-K Similarity Search)

對應 JD： 圖片搜尋、利用雲端…優化演算法效能 核心考點： 高維向量計算、資料結構 (Min-Heap / Priority Queue)、複雜度優化。

情境： App 有一個功能是「找相似貼圖」。每張圖片都已經被 AI 轉換成一個 128 維的特徵向量 (Feature Vector)。 請實作一個函式，從資料庫的 100 萬個向量中，找出與 query_vector 最像的 K 個結果。 (請使用 Cosine Similarity 計算相似度，並用 Min-Heap 優化排序過程，不要直接 Sort 整個陣列)。

code
FUNCTION FindTopKSimilarImages(
    k: Integer,
    query_vector: Array of Float,
    database_vector: Map<ID, Array of Float>
) -> OUTPUT: List of IDs

    // 1. create min heap
    min_heap = NEW MinHeap()

    // 2. precalculate magnitude of query vector
    query_mag = CALCULATE_MAGNITUDE(query_vector)

    // 3. Iterate through all vector in database
    FOR EACH id, db_vector IN database_vector DO

        // calculate cosine similarity
        // (A . B) / (|A| * |B|)
        dot_product = DOT_PRODUCT(query_vector, db_vector)
        db_mag = CALCULATE_MAGNITUDE(db_vector)

        IF db_mag == 0 OR query_mag == 0 THEN
            similarity = 0
        ELSE
            similarity = dot_product / (db_mag * query_mag)
        END IF
        
        // 4. Heap logic for top-k
        IF min_heap.size < k THEN
            min_heap.PUSH({
                id: id,
                score: similarity
            })
        ELSE
            lowest_score = min_heap.PEEK().score
            IF similarity > lowest_score THEN
                min_heap.POP()
                min_heap.PUSH({id: id, score: similarity})
            END IF
        END IF
    END FOR

    // 5. extract result and sort
    result_list = min_heap.TO_LIST()
    SORT result_list by score DESCENDING

    RETURN result _list
END FUNCTION

// calculate euclidean magnitude
FUNCTION CALCULATE_MAGNITUDE(vector: Array of Float)
    sum_square = 0
    FOR val IN vector DO
        sum_square = sum_square + (val * val)
    END FOR

    RETURN SQRT(sum_square)
END FUNCTION

insert, delete both O(log K)
Thus total time complexity is O(N log K)